最大半连通子图

Time Limit: 30 Sec Memory Limit: 162 MB

Description

一个有向图G=(V,E)称为半连通的(Semi-Connected)：

如果满足：∀u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。

若G’=(V’,E’)满足V’∈V，E’是E中所有跟V’有关的边，则称G’是G的一个导出子图。

若G’是G的导出子图，且G’半连通，则称G’为G的半连通子图。

若G’是G所有半连通子图中包含节点数最多的，则称G’是G的最大半连通子图。

给定一个有向图G，请求出G的最大半连通子图拥有的节点数K ，以及不同的最大半连通子图的数目C。

由于C可能比较大，仅要求输出C对X的余数。

Input

第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。

接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。

Output

应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

Sample Input

6 6 20070603
　1 2
　2 1
　1 3
　2 4
　5 6
　6 4

Sample Output

3
　　3

HINT

N ≤100000, M ≤1000000；对于100%的数据， X ≤10^8

Main idea

求最大半联通子图大小与个数。（最大半联通子图定义：在这个图内对于任意节点u,v，存在一条u->v的路径）

Solution

先跑一遍Tarjan，得到了两两连通的图，然后考虑如何加入单向连通的点集，显然两个强连通分量之间要是有连边的话，就可以满足这两个强连通分量的点单向连通，符合题意。

那么答案显然就是在缩点后的DAG（有向无环图）上的最长路径。

用拓扑+DP（本质是在拓扑序上的DP）可以求出即为Ans，然后在跑的时候用一个数组f[i]统计一下相同的个数，注意更新dist的时候也要更新f，最后如果dist[i]=Ans，那么累加f[i]，即为答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<bits/stdc++.h>
using namespace std;

const int ONE=2000001;

int n,m,MOD;
int x,y;
int Next[ONE],First[ONE],Go[ONE],tot;
int next[ONE],first[ONE],go[ONE],Input[ONE];
int dist[ONE];
int T,t;
int tou,wei,jishu;
int q[ONE];
int Ans,num,f[ONE];
int Dfn[ONE],Low[ONE],vis[ONE],F[ONE],Num[ONE];

struct power
{
    int u,v;
}a[ONE];

int cmp(const power &a,const power &b)
{
    if(a.u==b.u) return a.v<b.v;
    return a.u<b.u;
}

int rule(const power &a,const power &b)
{
    return (a.u==b.u && a.v==b.v);
}

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Add(int u,int v)
{
    Next[++tot]=First[u];   First[u]=tot;   Go[tot]=v;
}

int Add_edge(int u,int v)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  Input[v]++;
}

void Tarjan(int u)
{
    Dfn[u]=Low[u]=++T;
    vis[u]=1;
    q[++t]=u;
    int v;
    for(int e=First[u];e;e=Next[e])
    {
        int v=Go[e];
        if(!Dfn[v])
        {
            Tarjan(v);
            Low[u]=min(Low[u],Low[v]);
        }
        else    if(vis[v])
            Low[u]=min(Low[u],Dfn[v]);
    }

    if(Low[u]==Dfn[u])
    {
        jishu++;
        do
        {
            v=q[t--];
            F[v]=jishu;
            vis[v]=0;
            Num[jishu]=Num[jishu]+1;
        }while(v!=u);
    }
}

void Rebuild()
{
    num=0;
    for(int u=1;u<=n;u++)
    {
        for(int e=First[u];e;e=Next[e])
        {
            int v=Go[e];
            if(F[u]!=F[v])
            {
                a[++num].u=F[u];
                a[num].v=F[v];
            }
        }
    }

    sort(a+1,a+num+1,cmp);
    num=unique(a+1,a+num+1,rule)-1-a;

    for(int i=1;i<=num;i++)
    {
        Add_edge(a[i].u,a[i].v);
    }
}

void Topufirst()
{
    for(int v=1;v<=jishu;v++)
    {
        if(!Input[v]) q[++wei]=v;
        dist[v]=Num[v];
        f[v]=1;
        Ans=max(Ans,dist[v]);
    }
}

void TopuA()
{
    while(tou<wei)
    {
        int u=q[++tou];
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(dist[v]<dist[u]+Num[v])
            {
                dist[v]=dist[u]+Num[v];
                f[v]=f[u];
                Ans=max(Ans,dist[v]);
            }
            else
                if(dist[v]==dist[u]+Num[v]) f[v]=(f[v]+f[u])%MOD;
            if(!(--Input[v])) q[++wei]=v;
        }
    }
}

int main()
{
    n=get();    m=get();    MOD=get();
    for(int i=1;i<=m;i++)
    {
        x=get();    y=get();
        Add(x,y);
    }

    for(int i=1;i<=n;i++)
        if(!Dfn[i]) Tarjan(i);

    tot=0;
    Rebuild();

    tou=0;  wei=0;
    Topufirst(); TopuA();

    tot=0;
    for(int i=1;i<=jishu;i++)
        if(dist[i]==Ans) tot=(tot+f[i])%MOD;

    printf("%d\n%d",Ans,tot);
}